/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
// 使用中序非递归形式
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        if (!root)
            return -1;
        int cnt = 0;
        int ans=0;
        stack<TreeNode*> S;
        TreeNode* rt = root;
        while (rt || !S.empty()) {
            while(rt)
            {
                S.push(rt);
                rt=rt->left;
            }
            rt=S.top();
            if(++cnt==k)
                return rt->val;
            S.pop();
            rt=rt->right;
        }
        return -1;
    }
};

//方法二递归
//使用递归形式
class Solution {
public:
int ans=-1;
void inorder(TreeNode* root,int& k)
{
    if(!root||k==0) return;
    inorder(root->left,k);
    k--;
    if(k==0)
    {
        ans= root->val;
        return;
    }
    inorder(root->right,k);      
}
    int kthSmallest(TreeNode* root, int k) {
        inorder(root,k);
        return  ans;
    }
};
